424. 替换后的最长重复字符

Similar Question

leading to the advanced question

Solution Tips

方案一: 滑动窗口

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var characterReplacement = function(s, k) {
    // 窗口内去确认主字符, 通过贪心思想, 认为数量最多的是主字符
    // 因为主字符可能随着窗口的扩大而切换, 因此需要记录每个字符出现的个数, 并计算非主字符的总数
    // 保证非主字符的总数小于等于 k, 此时主字符的重复子串最长
    let left = 0;
    let right = 0;
    const map = {};
    let max = 0;
    let maxChar = '';
    let sum = 0;
    let rest = 0;

    let maxLen = 0;

    while (right < s.length) {
        const char = s[right];
        map[char] = (map[char] || 0) + 1;
        // 计算主字符数和非主字符数
        // 因为字符是一个个增加的, 所以只需要维护一个 max 和 sum 即可
        // 当新的字符超过了 max 时, 同样是 max++ 和 sum++
        sum++;
        if (map[char] > max) {
            max = map[char];
            maxChar = char;
        };
        rest = sum - max;
        if (rest <= k) {
            // 这个窗口的极限到了, 更新长度
            maxLen = Math.max(maxLen, right - left + 1);
        }

        if (rest > k) {
            // 调整左侧的窗口大小
            const leftChar = s[left];
            --map[leftChar];
            sum--;
            // max 好像没办法更新... 其实 max 只要能--就行, rest 可以直接算出来
            // maxChar 发生了变化好像没办法计算出来
            // 所以这里还是乖乖走 map 解析吧
            const [newMaxChar, newMax] = getMax(map);
            max = newMax;
            maxChar = newMaxChar;
            left++;
        }

        right++;
    }

    return maxLen;

    function getMax(map) {
        return Object.entries(map).reduce((max, [key, value]) => value > max[1]? [key, value] : max, ['', 0])
    }
};

方案二: 官解 Case 优化

实际上, 窗口的大小再达到最大之后会不会再缩小了, 因为假如后面的都是不符合条件的 right 每增大一位, left 就得马上缩小一位

所以官解最后返回了 right - left

类似的原因, 导致 maxChar 也不需要在 left++ 的时候更新, 因为如果新的 char 没有超过之前的 maxChar 最终返回值是不会更新的.

因此有了官解这个更加简洁的解法:

var characterReplacement = function(s, k) {
    const num = new Array(26).fill(0);
    const n = s.length;
    let maxn = 0, left = 0, right = 0;

    while (right < n) {
        num[s[right].charCodeAt() - 'A'.charCodeAt()]++;
        maxn = Math.max(maxn, num[s[right].charCodeAt() - 'A'.charCodeAt()])
        if (right - left + 1 - maxn > k) {
            num[s[left].charCodeAt() - 'A'.charCodeAt()]--;
            left++;
        }
        right++;
    }
    return right - left;
};